package com.singzi.algorithm;

import java.util.HashSet;

public class KMP {
    public void getNext(int[] next, String s){

        int j = 0;
        next[0] = 0;
        for (int i = 1;i < s.length();i++)
        {
            while (j > 0 && s.charAt(i)!=s.charAt(j))
            {
                j = next[j-1];
            }
            if (s.charAt(i) == s.charAt(j))
            {
                j++;
            }

                next[i] = j;
        }
    }
    public int strStr(String haystack, String str)

    {
        HashSet<Character> set = new HashSet<>();

        int[] next = new int[str.length()];
        getNext(next, str);
        int j = 0;
        for(int i = 0; i<haystack.length(); i++)
        {
            while (j > 0 && str.charAt(j) != haystack.charAt(i)){
                j = next[j-1];
            }
            if(str.charAt(j) == haystack.charAt(i)) {
                j++;
            }
            if (j == str.length())
            {
                return (i - str.length() + 1);
            }

        }
        return -1;
    }
}
